open Types
open Utils
open Cfg

(** {2 Fonctions concernant l'analyse des variables actives/vivantes} *)

(** {3 Fonctions utiles et d'affichage} *)


(** [get lst ind] permet de récupérer la liste des variables actives IN/OUT pour un label 
    @param lst la liste de tous les labes
    @param ind le label concerné
*)
let rec lv_get lst ind : Types.ln_elt = match lst with
  | [] -> {lbl= ind ; _in=[] ; out=[]}
  | Liveness(a)::l -> if a.lbl == ind then a else lv_get l ind

(** [lv_set lst pelt] permet de modifier la liste des variables actives IN/OUT pour un label 
    @param lst la liste de tous les labes
    @param pelt la nouvelle liste de variables actives IN/OUT
*)
let rec lv_set lst (Liveness(elt')) = 
  let elt = Liveness({elt' with 
      _in=uniq elt'._in ;
      out=uniq elt'.out
    })  in 
          lv_set_aux lst elt elt'.lbl
and lv_set_aux lst elt lbl = 
  match lst with
  | [] -> elt::[]
  | Liveness(a) as a'::l -> if a.lbl == lbl then 
      elt::l
    else
      a'::(lv_set_aux l elt lbl)

(** [print_liveness] affiche un élément de résultat de l'analyse*)
let print_liveness ln cur prefix  = 
    print_string ((string_of_int cur)^": ");
    print_string prefix ;
    let space = get_space 50 (String.length prefix) in 
      print_string (String.make space ' ') ;
      let elt = lv_get ln cur in
        let s_in = string_of_var_list elt._in in 
          let space2 = get_space 20 (String.length s_in) in 
            print_string ("in: " ^s_in);
            print_string (String.make space2 ' ');
            print_endline ("out: "^(string_of_var_list elt.out))

(** [ln_equal ln1 ln2] détermine si 2 résultats d'une analyse de variables actives sont égaux. *)
let rec ln_equal ln1 ln2 = 
  if List.length ln1 != List.length ln2 then
    false
  else
    match ln1 with
    | [] -> true
    | a::ln1 -> ln_equal_aux2 a ln2
and ln_equal_aux vl1 vl2 = match vl1, vl2 with
  | [], [] -> true
  | [], _ | _, [] -> false
  | Var(a)::vl1, Var(b)::vl2 -> a = b && ln_equal_aux vl1 vl2
and ln_equal_aux2 a ln2 = 
  match ln2, a with
    | [],_ -> false
    | Liveness({lbl=i ; _in=vli1 ; out= vlo1})::ln2, 
      Liveness({lbl=j ; _in=vli2 ; out= vlo2}) -> if i == j then
        ln_equal_aux vli1 vli2 && ln_equal_aux vlo1 vlo2
      else 
        ln_equal_aux2 a ln2 


(** {3 Fonctions relatives à l'analyse} *)

(** [ln_gen lst ta] réalise la fonction "gen", ajoute toutes les variables contenu par ta dans lst. *)
let rec ln_gen lst ta = match ta with
  | [] -> lst
  | a::ta -> a::(ln_gen lst ta)

(** [ln_kill lst ta] réalise la fonction "kill", supprimes toutes les variables contenu par td dans lst. *)
let rec ln_kill lst td = match td with
  | [] -> lst
  | a::td -> ln_kill_aux lst a
and ln_kill_aux lst a = match lst, a with
  | [], _ -> []
  | Var(b)::l, Var(a') -> let nl = ln_kill_aux l a in
                            if a' = b then nl else Var(b)::nl

(** Contient le résultat de l'analyse *)
let lv_ana = ref []

(** [lv p flw cur] propage les variables actives dans l'instruction "cur" du programme "p" dont le flow est "flw"*)
let lv p flw cur = let instr = get_instr p cur in 
  if List.exists (fun b -> b == cur) (final p) then
    lv_ana := lv_set !lv_ana (Liveness({
      lbl= cur ;
      _in= ln_gen [] (get_used_var instr) ;
      out= []
    }))
  else
    let s = succ flw cur in 
      let sln = List.map (fun c -> match c with | Liveness(c) -> c._in) (
        List.filter (
          fun a -> match a with | Liveness(a) -> 
            (List.exists (fun b -> 
              a.lbl == b
            ) s)
        ) !lv_ana) in 
        let out = List.flatten sln in 
          lv_ana := lv_set !lv_ana (Liveness({
            lbl= cur;
            _in= ln_gen (ln_kill out (get_defs_var instr)) (get_used_var instr) ;
            out= out
          }))
